package com.zds.leetcode;

import java.util.ArrayList;
import java.util.List;

public class q_23 {
    public static void main(String[] args) {
        q_23 q = new q_23();
        // lists = [[1,4,5],[1,3,4],[2,6]]
        ListNode[] listNodes = {
                new ListNode(1, new ListNode(4, new ListNode(5))),
                new ListNode(1, new ListNode(3, new ListNode(4))),
                new ListNode(2, new ListNode(6))
        };

        ListNode listNode = q.mergeKLists(listNodes);
        System.out.println(listNode);
    }

    public ListNode mergeKLists(ListNode[] lists) {
        // 遍历所有这些链表的 list 如果哪一个遍历到了空，使用 remove
        List<ListNode> listNodes = new ArrayList<>();
        for (ListNode list : lists) {
            if (list != null) {
                listNodes.add(list);
            }
        }
        ListNode head = new ListNode();
        ListNode cur = head;
        while (listNodes.size() > 0) {
            int min = Integer.MAX_VALUE;
            int minIndex = 0;
            for (int i = 0; i < listNodes.size(); i++) {
                ListNode listNode = listNodes.get(i);
                if (listNode.val < min) {
                    min = listNode.val;
                    minIndex = i;
                }
            }
            cur.next = listNodes.get(minIndex);
            cur = cur.next;
            listNodes.set(minIndex, listNodes.get(minIndex).next);
            if (listNodes.get(minIndex) == null) {
                listNodes.remove(minIndex);
            }
        }
        return head.next;
    }
}
